1. Field of the Invention
The present invention relates to an apparatus and a method for receiving a signal in a communication system, and more particularly to an apparatus and a method for receiving a signal in a communication system using a non-binary Low Density Parity Check (LDPC) code, which decodes the non-binary LDPC code while minimizing the memory capacity required for performing a check node operation.
2. Description of the Related Art
Next-generation communication systems have evolved from a packet service communication system for transmitting burst packet data to a plurality of Mobile Stations (MSs), with the packet service communication system being suitable for mass data transmission. Further, next-generation communication systems are considering a LDPC code, together with a turbo code, as a channel code. The LDPC code is known to have an excellent performance gain at high-speed data transmission, and advantageously enhances data transmission reliability by effectively correcting an error due to noise occurring in a transmission channel. Examples of next-generation communication systems positively considering the use of the LDPC code include the IEEE (Institute of Electrical and Electronics Engineers) 802.16e communication system, the IEEE 802.11n communication system, etc.
Reference will now be made to the structure of a signal transmission apparatus in a common communication system using a LDPC code, with reference to FIG. 1.
FIG. 1 is a block diagram illustrating the structure of a signal transmission apparatus in a common communication system using a LDPC code. Referring to FIG. 1, the signal transmission apparatus includes an encoder 111, a modulator 113 and a transmitter 115. First, if an information vector s to be transmitted occurs in the signal transmission apparatus, the information vector s is delivered to the encoder 111. The encoder 111 generates a codeword vector c, that is, a LDPC codeword by encoding the information vector s in a predetermined encoding scheme, and then outputs the generated codeword vector c to the modulator 113. Here, the predetermined encoding scheme corresponds to a LDPC encoding scheme. The modulator 113 generates a modulation vector m by modulating the codeword vector c in a predetermined modulation scheme, and then outputs the generated modulation vector m to the transmitter 115. The transmitter 115 inputs therein the modulation vector m output from the modulator 113, executes transmission signal processing for the input modulation vector m, and then transmits the processed modulation vector m to a signal reception apparatus through an antenna.
Next, reference will be made to the structure of a signal reception apparatus in a common communication system using a LDPC code, with reference to FIG. 2.
FIG. 2 is a block diagram illustrating the structure of a signal reception apparatus in a common communication system using a LDPC code. Referring to FIG. 2, the signal reception apparatus includes a receiver 211, a demodulator 213 and a decoder 215. First, a signal transmitted by a signal transmission apparatus is received through an antenna of the signal reception apparatus, and the received signal is delivered to the receiver 211. The receiver 211 executes reception signal processing for the received signal to thereby generate a reception vector r, and then outputs the processed and generated reception vector r to the demodulator 213. The demodulator 213 inputs therein the reception vector r output from the receiver 211, generates a demodulation vector x by demodulating the input reception vector r in a demodulation scheme corresponding to a modulation scheme applied to a modulator of the signal transmission apparatus, that is, the modulator 113, and then outputs the generated demodulation vector x to the decoder 215. The decoder 215 inputs therein the demodulation vector x output from the demodulator 213, decodes the input demodulation vector x in a decoding scheme corresponding to an encoding scheme applied to an encoder of the signal transmission apparatus, that is, the encoder 111, and then outputs the decoded demodulation vector x into a finally restored information vector s. Here, the decoding scheme, that is, a LDPC scheme, is a scheme using an iterative decoding algorithm based on a sum-product algorithm. The sum-product algorithm will be described below in detail.
A binary LDPC code is a code defined by a parity check matrix in which most elements have a value of 0, but a small minority of other elements have a non-zero value, for example, a value of 1. Thus, all the elements constituting the parity check matrix of the binary LDPC code have a value of 0 or 1. In contrast with this, all elements constituting the parity check matrix of a non-binary LDPC code are elements in a Galois Field of order q (hereinafter referred to as “GF(q)”). Here, “q” in GF(q) indicates the order of a GF, and q=2p. Thus, the non-binary LDPC code is a code defined by a parity check matrix in which most elements have a value of 0, but a small minority of other elements are non-zero elements, for example, elements of GF(q).
Further, a codeword of the non-binary LDPC code, C, is a vector having a length of N and including elements of GF(q), and satisfies Equation (1):
                                                        ∑                              i                =                1                            N                        ⁢                                                  ⁢                                          h                ji                            ⁢                              c                i                                              =          0                ,                  ∀                      j            ∈                          {                              1                ,                ⋯                ⁢                                                                  ,                M                            }                                                          (        1        )            
In Equation (1), hji denotes an element existing in a jth row and an ith column of the parity check matrix of the non-binary LDPC code, ci denotes an ith element of the codeword C, M denotes the number of rows of the parity check matrix, and N denotes the number of columns of the parity check matrix.
If it is assumed that a jth row of the parity check matrix includes three non-zero elements and the three non-zero elements are hji1, hji2, hji3, respectively, then a codeword C satisfies Equation (2):(hji1{circle around (x)}ci1)⊕(hji2{circle around (x)}ci2)⊕(hji3{circle around (x)}ci3)=0   (2)
In Equation (2), ⊕ denotes an additive operation on GF(q), and {circle around (x)} denotes a multiplicative operation on GF(q).
In general, a polynomial representation is used as a scheme for expressing elements of GF(2p). Coefficients of GF(2p) are generated from a pth degree irreducible polynomial which is defined in GF(2), and all elements of GF(2p) are expressed by a (p−1)th degree polynomial whose coefficients are defined in GF(2). GF(2p) will now be described by exemplifying GF(24).
First, GF(24) is generated from a fourth-order irreducible polynomial p(x)=x4+x+1. Here, if it is assumed that a root of the fourth-order irreducible polynomial p(x)=x4+x+1 is α, all elements of GF(24) are equal to {0, 1, α, α2, α3, . . . , α14}. Further, all the elements of GF(24) can be expressed by at most a third-order polynomial α3x3+α2x2+α1x+α0, the coefficients of which are defined in GF(2).
All the elements {0, 1, α, α2, α3, . . . , α14} of GF(24), the polynomial coefficients {α3, α2, α1, α0}, and decimal expressions corresponding thereto are shown below in Table 1.
TABLE 1elementa3a2a1a0decimal number000000100011α00102α201004α310008α400113α501106α6110012α7101111α801015α9101010α1001117α11111014α12111115α13110113α1410019
In addition, the LDPC code can be expressed using a bipartite graph which is represented by variable nodes, check nodes and edges connecting the variable nodes and the check nodes with each other.
Further, the LDPC code can be decoded on the bipartite graph by using an iterative decoding algorithm based on a sum-product algorithm. Here, the sum-product algorithm is a type of message passing algorithm, and the message passing algorithm refers to an algorithm in which messages are exchanged on the bipartite graph through the edges, and an output message is calculated and updated from messages input into the variable nodes or the check nodes. That is, since a decoder for decoding the LDPC code uses the iterative decoding algorithm based on the sum-product algorithm, it is less complex than a decoder for decoding a turbo code, and can be easily implemented as a parallel processing decoder.
In a bipartite graph of a non-binary LDPC code defined in GF(2p), a variable node is a random variable of GF(2p), and a message passed through an edge is a vector with a size of 2p. Each element included in the vector with a size of 2p indicates the probability that the random variable has each of a 2p number of elements of GF(2p).
Reference will now be made to the permutation of a message vector with the value of an edge in a non-binary LDPC code, with reference to FIG. 3.
FIG. 3 illustrates explains the permutation of a message vector with the value of edge in an ordinary non-binary LDPC code Referring to FIG. 3, variable node i and check node j are connected by an edge, and the edge connecting the variable node i and the check node j has a value of hji which is an element of GF(2p). To mention that the edge connecting the variable node i and the check node j has a value of hji implies that an element existing in a jth row and an ith column of a parity check matrix defined in GF(2p) is hji. Here, a message, which is passed through the edge connecting the variable node i and the check node j, is a vector with a size of 2p, and each element {P0, . . . , Pq−1} included in the message vector with a size of 2p indicates the probability that the variable node i has each element of GF(2p). The message vector is permuted with the edge's value hji, and elements included in the permuted message vector become {P0×hji, . . . P(q−1)×hji} in sequence. Here, a multiplicative operation is defined on GF(2p), and decimal numbers {0, 1, . . . , q−1} indicate elements of GF(2p), expressed by the polynomial representation as shown above in Table 1.
Reference will now be made to the inner structure of a decoder in the case of decoding a non-binary LDPC code by using a sum-product algorithm, with reference to FIG. 4.
FIG. 4 is a block diagram illustrating the inner structure of a decoder for decoding an ordinary non-binary LDPC code. Before explaining FIG. 4, it should be noted that although the decoder generally includes a check node processing unit and a variable node processing unit, only the structure of the check node processing unit of the decode is illustrated in FIG. 4. Referring to FIG. 4, a node processing unit within the decoder includes a first shuffle network processing unit 410, a check node processor 440 and a second shuffle network processing unit 470.
The first shuffle network processing unit 410 includes a plurality of multipliers, for example, a dc number of multipliers, that is, a multiplier 411-1 through multiplier 411-dc, and a plurality of FFT (Fast Fourier Transform) units, for example, a dc number of FFT units, that is, an FFT unit 413-1 through an FFT unit 413-dc.
The second shuffle network processing unit 470 includes a plurality of IFFT (Inverse Fast Fourier Transform) units, for example, a dc number of IFFT units, that is, an IFFT unit 471-1 through an IFFT unit 471-dc, and a plurality of multipliers, for example, a dc number of multipliers, that is, a multiplier 473-1 through a multiplier 473-dc.
The operation of the check node processing unit will now be described by exemplifying a jth check node in the parity check matrix of a non-binary LDPC code. Here, the degree of the jth check node is assumed to be dc.
First, if it is assumed that input messages input into the first shuffle network processing unit 410 are
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,      ϰ          i              d        c              ,the input messages
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,      ϰ          i              d        c            are messages passed from a variable node to a check node, and each input message
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,      ϰ          i              d        c            is a vector with a size of 2p. The input messages
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,      ϰ          i              d        c            are input into the multiplier 411-1, the multiplier 411-2, the multiplier 411-3, . . . and the multiplier 411-dc, respectively.
Each of multiplier 411-1 through multiplier 411-dc performs multiplication of each input message vector
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,      ϰ          i              d        c            and each edge value
      h          ji      1        ,      h          ji      2        ,  ⋯  ⁢          ,      h          ji              d        c            of the parity check matrix on GF(2p). However, since the input messages are not elements on GF(2p), but indicate the probabilities of having the elements on GF(2p), each of multiplier 411-1 through multiplier 411-dc actually performs the permutation of each input message
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,            ϰ              i                  d          c                      .  Here, a 2p×2p number of unit memories are required for storing the permutation information. Further, since each unit memory consists of p bits, a memory capacity capable of storing total 2p×2p×p bits is consequently required for storing the permutation information.
After the permutation, each of multiplier 411-1 through multiplier 411-dc outputs each permuted input message
      ϰ          i      1        ,      ϰ          i      2        ,  ⋯  ⁢          ,      ϰ          i              d        c            to each of the FFT unit 413-1 through FFT unit 413-dc. Each of FFT unit 413-1 through FFT unit 413-dc inputs therein a signal output from each of multiplier 411-1 through multiplier 411-dc, performs FFT for the input signal, and then outputs the fast Fourier transformed signal to the check node processor 440. Here, the signal input into each of FFT unit 413-1 through and FFT unit 413-dc is the probability of each element expressed by the polynomial representation as defined above in Table 1. Further, the FFT performed in each of FFT unit 413-1 through FFT unit 413-dc means not ordinary FFT, but FFT performed on GF(2p), which is identical to Fast Hadamard Transform (“FHT”).
The check node processor 440 inputs therein a signal output from each of FFT unit 413-1 through FFT unit 413-dc, performs a check node operation, and then outputs a corresponding result to each of IFFT unit 471-1 through IFFT unit 471-dc. Each of IFFT unit 471-1 through IFFT unit 471-dc inputs therein a signal output from the check node processor 440, performs IFFT for the input signal, and outputs the inverse fast Fourier transformed signal to each of the multiplier 473-1, the multiplier 473-2, the multiplier 473-3, . . . and the multiplier 473-dc. Here, the IFFT performed in each of IFFT unit 471-1 through IFFT unit 471-dc means not ordinary IFFT, but IFFT performed on GF(2p). Further, each of IFFT unit 471-1 through IFFT unit 471-dc has the same structure as that of each of FFT unit 413-1 through FFT unit 413-dc, except that an output thereof is scaled by ½p.
Each of multiplier 473-1 through multiplier 473-dc inputs therein a signal output from each of IFFT unit 471-1 through IFFT unit 471-dc, and performs multiplication of the input signal and the multiplicative inverse element
      h          ji      1              -      1        ,      h          ji      2              -      1        ,  ⋯  ⁢          ,      h          ji              d        c                    -      1      of each edge value
      h          ji      1        ,      h          ji      2        ,  …  ⁢          ,      h          ji              d        c            of the parity check matrix on GF(2p). Here, each of multiplier 473-1 through multiplier 473-dc also actually performs the permutation of the signal output from each of IFFT unit 471-1 through IFFT unit 471-dc, and this permutation corresponds to the inverse of the permutation performed in each of multiplier 411-1 through multiplier 411-dc. Hereinafter, for the convenience of explanation, the permutation performed in each of multiplier 473-1 through multiplier 473-dc will be referred to as “inverse permutation”. Thus, a 2p×2p number of unit memories are required for storing the inverse permutation information. Further, since each unit memory consists of p bits, a memory capacity capable of storing total 2p×2p×p bits is consequently required for storing the inverse permutation information. Since it is possible to extract one of the permutation information and the inverse permutation information from the other, it does not matter if only one of them is stored.
As stated above, in order to perform a check node operation, a memory capacity capable of storing 2p×2p×p bits is required for storing permutation information or inverse permutation information. Therefore, there is a strong need for decoder which makes it possible to reduce the memory capacity required for the check node operation.